
import java.util.ArrayList;

// Create node class for board class that contains its
// row and column value
class ListNode {
	int row;
	int col;
	ListNode prev;
	boolean visited;
	
	ArrayList<ListNode> neighbours = new ArrayList<ListNode>();
	
	public ListNode(int r, int c) {
		row = r;
		col = c;
		visited = false;
	}
}

// Adjacency list class that holds the graph of possible
// jump moves.
public class AdjList {
	ArrayList<ListNode> list = new ArrayList<ListNode>();
	HashTable table;
	private int numEdge = 0;
	private int numVertex = 0;
	private int listSize = 0;
	
	public AdjList(int size) {
		table = new HashTable(size);
	}
	
	
	// Inserts a board position into the adjacency list.
	// Also inserts position into a hashtable.
	// Returns false if it is already in the list
	// otherwise return true.
	public boolean insert(int row, int column) {
		if (doesExist(row, column))
			return false;
		
		ListNode node = new ListNode(row, column);
		list.add(node);
		numVertex++;
		table.insert(row, column, listSize);
		listSize++;
				
		return true;
	}
	
	// Returns the list of jump moves for a board position
	// at [row][col] using a hashtable to get the index
	// position in the adjacency list
	public ArrayList<ListNode> neighbourOf(int row, int col) {
		return list.get(table.position(row, col)).neighbours;
	}
	
	// Checks to see if the board position at [row][col] already 
	// exists in the adjacency list. This is achieved by seeing 
	// if it is already contained in the hashtable for this list.
	public boolean doesExist(int row, int col) {
		if (table.doesExist(row, col))
			return true;
		
		return false;
	}
	
	//Checks to see if row1, col1 are neighbours of row2,col2 and returns
	// true if so, false otherwise
	// Note: By neighbours, it means possible jump.
	public boolean isNeighbourOf(int row1, int col1, int row2, int col2){
		int position = index(row1,col1);
		
		// position of row1 and col1 does not have possible jumps moves from it
		if (position<0) {
			return false;
		}
		
		ArrayList<ListNode> neighbours = list.get(position).neighbours;
		int i = 0;
		
		// cycle through the neighbours of row1,col1 to see if row2,col2 is a
		// possible jump from it
		while (i < neighbours.size()){
			if (neighbours.get(i).row==row2 && neighbours.get(i).col==col2){
				return true;
			}
			i++;
		}
		
		return false;
	}
	
	// Returns postition of row, col in adjacency list using the hash table
	// Returns -1 if row, col arent in adjacency list
	private int index(int row, int col) {
		if (table.doesExist(row, col))
			return table.position(row, col);
		
		return -1;
	}
	
	// Creates an edge from [row1][col1] to [row2][col2]
	// (used to indicate jump move). Uses hashtable to find
	// index of [row1][col1] in the adjacency list.
	public void insertNeighbour(int row1, int col1, int row2, int col2) {
		ListNode node = new ListNode(row2, col2);
		list.get(table.position(row1, col1)).neighbours.add(node);
		numEdge++;
	}
	
	// Removes the edge from [row1][col1] to [row2][col2]
	// Uses hashtable to find index of [row1][col1] in list.
	// Returns false if either position doesn't exist (aren't
	// possible jump moves) or there isn't an edge between them
	public boolean removeNeighbour(int row1, int col1, int row2, int col2) {
		int parentPos = index(row1,col1);
		
		if (parentPos < 0){
			return false; 
		}
		
		for (int num = 0; num < list.get(parentPos).neighbours.size(); num++) {
			if (list.get(parentPos).row == row2 && list.get(parentPos).col == col2) {
				list.get(parentPos).neighbours.remove(num);
				return true;
			}
		}
		
		return false;
	}
	
	// Returns the number of edges in the adjacency list (or jump moves)
	public int numEdges() {
		return numEdge;
	}
	
	// Returns the number of vertices in the adjacency list
	public int numVertices() {
		return numVertex;
	}
	
	
	// Runs a DFS search on the adjacency list of the possible
	// jump moves given the player
	public Move[] DFS(int player) {
		// No possible jump moves
		if (numVertex == 0) {
			return null;
		}
		
		ArrayList<Move> jumpMoves = new ArrayList<Move>();
		ArrayList<Integer> rows = new ArrayList<Integer>();
		ArrayList<Integer> columns = new ArrayList<Integer>();
		
		int i = 0;
		
		// Gets the first jump position that is available in
		// the list
		ListNode current = list.get(i);
		ListNode previous = null;
		rows.add(current.row);
		columns.add(current.col);
		
		// Traverses along neighbouring vertices till vertex is
		// reached with no neighbours. Adds the jump moves upto
		// that position then cycles back to previous node and
		// has it's position deleted from this node. Cycles
		// through until every vertex has no neighbour.
		while (i < numVertices()) {
			for(int numNeighbours = 0; numNeighbours<current.neighbours.size(); numNeighbours++){
				previous = current;
				current = current.neighbours.get(numNeighbours);
				rows.add(current.row);
				columns.add(current.col);
				if (current.neighbours.size() == 0) {
					int row[] = new int[rows.size()];
					int col[] = new int[columns.size()];
					for (int l=0; l<columns.size();l++) {
						row[l] = rows.get(l);
						col[l] = columns.get(l);
					}
					
					Move move = new Move(player, false, row, col);
					jumpMoves.add(move);
					removeNeighbour(previous.row,previous.col,current.row,current.col);
					rows.remove(rows.size()-1);
					columns.remove(columns.size()-1);
					current = previous;
				}
			}
			i++;
		}
		
		Move[] jumpers = new Move[jumpMoves.size()];
		
		// converts arraylist into a array of type Move
		for (int p=0; p<jumpMoves.size(); p++) {
			jumpers[p] = jumpMoves.get(p);
		}
		
		return jumpers;
	}
}